#include <bits/stdc++.h>

using namespace std;

const int N = 1e7;
class Solution
{
  public:
    int dfs(vector<int> &nums, int start, int end, vector<int>& mem)
    {
        if (start > end)
            return 0;
        if (mem[start] != -1)
            return mem[start];
        int take = dfs(nums, start + 2, end, mem) + nums[start];
        int no_take = dfs(nums, start + 1, end, mem);
        return mem[start] = max(take, no_take);
    }
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        // vector<int> mem1(n + 2, -1);
        // vector<int> mem2(n + 2, -1);
        // if (n == 0)
        //     return 0;
        // int ans = max(dfs(nums, 0, n - 2, mem1), dfs(nums, 1, n - 1, mem2));
        // return ans;
        int ans = 0;
        vector<int> dp1(n + 2, 0);
        vector<int> dp2(n + 2, 0);
        //不拿第一家
        dp1[1] = nums[1];
        dp1[2] = max(nums[1], nums[2]);
        for (int i = 3; i < n; i++)
        {
            dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }
        //不拿最后一家
        dp2[0] = nums[0];
        dp2[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; i++)
        {
            dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);
        }
        return ans = max(dp1[n - 1], dp2[n - 2]);
        
    }
};
